#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
@File Name: 一个无价值的二叉搜索树_btree.py
@Author: LT
@Date: 2021/9/28 18:04
# -----------------------------------------------------------------------------------------------------
@Description: 
之所以叫二叉树是因为它内部的子树总是两个分叉。
它的节点实现是这样一个三元组：(LeftSubtree, NodeValue, RightSubtree)。

这个文件中类的解释：
· BinaryTree 本身是树的根节点，它初始化并管理真正的树，它有插入方法和查找方法。
· EmptyNode 是一个空对象，在树的底层空子树上使用。
· BinaryNode 是非空对象，它具有一个节点值和两个子树。

当向二叉树插入节点的时候，会用BinaryNode替换掉底层的EmptyNode。
应该不会再有比作者这个更简单的写树数据结构方法了
# -----------------------------------------------------------------------------------------------------
"""


class BinaryTree:
    def __init__(self): self.tree = EmptyNode()
    def __repr__(self): return repr(self.tree)
    def lookup(self, value): return self.tree.lookup(value)
    def insert(self, value): self.tree = self.tree.insert(value)


class EmptyNode:
    """
    EmptyNode的作用就是：
    在查找时：返回False
    在插入时：返回一个BinaryNode，并把自身作为该BinaryNode的左右叶子节点
    """
    def __repr__(self): return '*'
    def lookup(self, value): return False                               # 最底下的叶子节点一定是空，所以查找找不到的话最后会到空叶子节点，得返回False
    def insert(self, value): return BinaryNode(self, value, self)


class BinaryNode:
    def __init__(self, left, value, right):
        self.left, self.data, self.right = left, value, right

    def lookup(self, value):
        if self.data == value:
            return True
        elif self.data > value:                                         # 在左子树查找
            return self.left.lookup(value)
        else:                                                           # 在右子树查找
            return self.right.lookup(value)

    def insert(self, value):
        if self.data > value:                                           # 添加到左子树
            self.left = self.left.insert(value)                         # self.left不管是EmptyNode类型还是BinaryNode类型，最后总会递归到EmptyNode的insert中去
        elif self.data < value:                                         # 添加到右子树
            self.right = self.right.insert(value)
        return self

    def __repr__(self):
        return '( %s, %s, %s )' % (repr(self.left), repr(self.data), repr(self.right))


if __name__ == '__main__':
    def main():
        x = BinaryTree()
        for i in [3, 1, 9, 2, 7]:
            x.insert(i)
    main()
    pass
